package leetcode_题库;

/**
 * Created by IntelliJ IDEA.
 *
 * @Author : Ding
 * @create 2022/9/21 16:01
 */
public class _134_加油站 {
    public static void main(String[] args) {
        int[] gas = new int[]{1,2,3,4,5};
        int[] cost = new int[]{3,4,5,1,2};
        System.out.println(canCompleteCircuit(gas, cost));
    }
    public static int canCompleteCircuit(int[] gas, int[] cost) {
        //定义最小值
        int min = Integer.MAX_VALUE;
        //定义累加
        int sum = 0;
        for (int i = 0; i < gas.length; i++) {
            sum += gas[i] - cost[i];
            //汽油亏损最大的点（差值最小值）
            min = Math.min(sum,min);
        }
        if (sum < 0){
            //总汽油不满足总消耗，则一定无解
            return -1;
        }
        if (min >= 0){
            //最小值大于0，说明在0位置出发恰好可以环绕一周，所以起点就是0位置
            return 0;
        }
        for (int i = gas.length - 1; i > 0; i--) {
            //从后面开始，补全差值
            min += gas[i] - cost[i];
            if (min >= 0){
                //当某一个点i满足补充了min使其不小于0，则起点就是i位置
                return i;
            }
        }
        return -1;
    }
}
